package slidingWindowAlgorithm;

import java.util.HashMap;

public class Class76_1 {

    public  String  minWindow(String s,String t){
        HashMap<Character, Integer> need = new HashMap<>();
        for (char c: t.toCharArray()
             ) {
            need.put(c,need.getOrDefault(c,0)+1);
        }

        HashMap<Character, Integer> window = new HashMap<>();
        int left=0,right=0;
        int valid=0;
        int size = s.length();
        int minLen=size+1;
        int start=0;


//        1、我们在字符串S中使用双指针中的左右指针技巧，初始化left = right = 0，把索引左闭右开区间[left, right)称为一个「窗口」。
//
//        2、我们先不断地增加right指针扩大窗口[left, right)，直到窗口中的字符串符合要求（包含了T中的所有字符）。
//
//        3、此时，我们停止增加right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同时，每次增加left，我们都要更新一轮结果。
//
//        4、重复第 2 和第 3 步，直到right到达字符串S的尽头。

        while (right<size){
            char c = s.charAt(right);
            right++;
            //  CKG TODO 2023/4/16: 遍历s 填充window   先找到一个含有need要求内容的 最小right
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(need.get(c))){
                    //  CKG TODO 2023/4/16: 统计s中是否有全部的t
                    valid++;
                }
            }
            int needSize = need.size();
            while (valid==needSize){
                //  CKG TODO 2023/4/16:遍历s开始寻找  start  minLen   找到含有t中要求元素的第一个位置
                c = s.charAt(left);
                left++;
                //  CKG TODO 2023/4/16: 选中s中含有t的开头元素
                if (need.containsKey(c)){
                    if (window.get(c).equals(need.get(c))){
                        valid--;
                    }
                    window.put(c,window.get(c)-1);
                }
                if (valid!=needSize){
                    if (right-left+1<minLen){
                        start=left-1;
                        minLen=right-left+1;
                    }
                }
            }
        }



        return  minLen==size+1?"":s.substring(start,start+minLen);

    }


    public static void main(String[] args) {
        Class76_1 class76_1 = new Class76_1();
        System.out.println(class76_1.minWindow("ADOBECODEBANC", "ABC"));


    }
}
